package thired.class09_union;
//https://leetcode.cn/problems/number-of-provinces/submissions/
public class Class02_FriendCircles {
    public class UnionSet{
        int[] parent;
        int[] size;
        int[] help;
        int sets;

        public UnionSet(int n){
            parent = new int[n];
            size = new int[n];
            help = new int[n];
            sets = n;
            for(int i = 0;i < n;i++){
                parent[i] = i;
                size[i] = 1;
            }
        }
        public int findFather(int cur){
            int h = 0;
            while(parent[cur] != cur){
                help[h++] = cur;
                cur = parent[cur];
            }
            for(h--;h >= 0; h--){
                parent[help[h]] = cur;
            }
            return cur;
        }
        public void union(int a,int b){
            int aHead = findFather(a);
            int bHead = findFather(b);
            if(aHead != bHead){
                if(size[aHead] >= size[bHead]){
                    parent[bHead] = aHead;
                    size[aHead] += size[bHead];
                }else{
                    parent[aHead] = bHead;
                    size[bHead] += size[aHead];
                }
                sets--;
            }
        }

        public int getsets(){
            return sets;
        }
    }
    public int findCircleNum(int[][] isConnected) {
        if(isConnected == null || isConnected.length == 0){return 0;}
        int N = isConnected.length;
        UnionSet union = new UnionSet(N);
        for(int i = 0; i < N;i++){
            for(int j = i + 1; j < N;j++){
                if(isConnected[i][j] == 1){
                    union.union(i,j);
                }
            }
        }
        return union.getsets();
    }
}
